Search for: All records

Synchronization of transaction pools (mempools) has shown potential for improving the performance and block propagation delay of state-of-the-art blockchains. Indeed, various heuristics have been proposed in the literature to incorporate early exchanges of unconfirmed transactions into the block propagation protocol. In this work, we take a different approach, maintaining transaction synchronization externally (and independently) of the block propagation channel. In the process, we formalize the synchronization problem within a graph theoretic framework and introduce a novel algorithm (SREP - Set Reconciliation-Enhanced Propagation) with quantifiable guarantees. We analyze the algorithm’s performance for various realistic network topologies, and show that it converges on static connected graphs in a time bounded by the diameter of the graph. In graphs with dynamic edges, SREP converges in an expected time that is linear in the number of nodes. We confirm our analytical findings through extensive simulations that include comparisons with MempoolSync, a recent approach from the literature. Our simulations show that SREP incurs reasonable bandwidth overhead and scales gracefully with the size of the network (unlike MempoolSync).